package A_sort;

/**
 * 快速排序
 */
public class E_QuickSort {
    public static void quickSort(int[] arr){
        if (arr==null||arr.length<2){
            return;
        }
        quickSort(arr,0,arr.length-1);
    }

    //L-R上排好序
    private static void quickSort(int[] arr,int L ,int R){
        if (L<R){
            //随机取L-R上的一个下标的位置当做划分值
            //如果不是随机而是默认某一个下标当做划分值，总有一种最差情况会出现，算法的时间复杂度为O(N^2)
            //随机取下标保证了样本无论什么情况都不会影响，其时间复杂度为O(N*logN)
            Swap.swap(L+(int)(Math.random()*(R-L+1)),R,arr);
            int[] p = partition(arr,L,R);
            quickSort(arr,L,p[0]-1);//<区
            quickSort(arr,p[1]+1,R);//>区
        }
    }

    //处理L-R上的函数
    //返回等于区的左右边界
    private static int[] partition(int[] arr,int L, int R){
        int smallIndex = L-1;//<区右边界
        int maxIndex = R;//>区左边界
        while (L< maxIndex){
            if (arr[L]<arr[R]){//当前值<划分值
                Swap.swap(++smallIndex,L++,arr);
            }else if(arr[L]>arr[R]){//当前值>划分值
                Swap.swap(--maxIndex,L,arr);
            }else{
                L++;
            }
        }
        Swap.swap(R,maxIndex,arr);
        return new int[] {smallIndex+1,maxIndex};
    }
}
